/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
/* 
方法思路
定义状态：设dp[i]为凑成金额i所需的最少硬币个数。
初始化：
dp[0] = 0，表示凑成金额 0 不需要任何硬币。
其余元素初始化为无穷大Infinity，表示暂时无法凑成该金额。
状态转移方程：对于每个金额i（从 1 到amount）和每个硬币面额coin，如果coin小于等于i，则可以选择使用该硬币，此时所需的最少硬币个数为dp[i - coin] + 1。我们需要遍历所有可能的硬币，取最小值：
dp[i]=min(dp[i],dp[i−coin]+1)
结果：如果dp[amount]仍然是无穷大，则表示无法凑成总金额，返回 - 1；否则返回dp[amount]。

代码解释
初始化 DP 数组：创建一个长度为amount + 1的数组dp，并将所有元素初始化为Infinity，除了dp[0]初始化为 0。
遍历金额：从 1 到amount遍历每个金额i。
遍历硬币：对于每个金额i，遍历每个硬币面额coin，如果coin小于等于i，则更新dp[i]为dp[i]和dp[i - coin] + 1中的较小值。
返回结果：如果dp[amount]仍然是Infinity，说明无法凑成总金额，返回 - 1；否则返回dp[amount]。
*/
var coinChange = function (coins, amount) {
  // 创建dp数组并初始化为无穷大
  const dp = new Array(amount + 1).fill(Infinity);
  // 凑成金额0需要0个硬币
  dp[0] = 0;

  // 遍历每个金额从1到amount
  for (let i = 1; i <= amount; i++) {
    // 遍历每个硬币面额
    for (const coin of coins) {
      if (coin <= i) {
        // 更新dp[i]为更小的值
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // 如果最终dp[amount]仍然是无穷大，说明无法凑成总金额
  return dp[amount] === Infinity ? -1 : dp[amount];
};